nLab pasting scheme

Idea

Pasting schemes are one possibility to give a rigorous treatment of the (older) notational device of pasting diagrams.

Notions of pasting scheme

More than one definition of pasting scheme has been used to give a justification to the practice of pasting diagrams.

For example, there are pasting schemes in the sense of Johnson 1987, and there are pasting schemes in the sense of Power 1990.

Power’s definition

Power’s notion is based on planar embeddings of quivers $Q$ that satisfy the following conditions:

• $Q$ is finite and connected;

• For the free category $F(Q)$ generated by $Q$, every endomorphism is an identity ($Q$ has no directed cycles);

• There are vertices $s, t$ of $Q$ (the source and sink, respectively) such that for every vertex $v$, the hom-sets $F(Q)(s, v)$ and $F(Q)(v, t)$ are inhabited (there exist directed paths in $Q$ from $s$ to $v$ and from $v$ to $t$).

We will call such quivers progressive, in rough analogy with progressive string diagrams.

There is a restricted geometric realization functor

$$Quiv = Set^{(0 \rightrightarrows 1)^{op}} \stackrel{skel}{\to} Set^{\Delta^{op}} \stackrel{R}{\to} Space$$

(into a convenient category of topological spaces $Space$) which we again denote as $R: Quiv \to Space$.

Definition

(after Power) A pasting scheme consists of a progressive quiver $Q$ together with an subspace embedding $i: R(Q) \hookrightarrow \mathbb{R}^2$, such that $i$ is a $C^1$ embedding on each edge interior.

To each pasting scheme $(Q, i)$ we may associate a 2-computad $C = Comp(Q, i)$. Part of the computad structure is easily described:

• The underlying quiver of $C$ is $Q$;

• The elements of $C_2$ (the 2-cells) are the bounded connected components of $\mathbb{R}^2 \setminus i(R(Q))$.

To complete the description of the computad, we need to define the source and target $\sigma(c), \tau(c) \in Mor(F(Q))$ of a 2-cell $c$. For each edge $e \in Q_1$ such that $i(e)$ lies in the boundary of $c$, and each interior point $x \in e$, we let $t(x) = i'(x)$ be the tangent vector, and $n(x)$ the inward-pointing normal (pointing into $c$); the $C^1$ embedding condition ensures that these make sense. Then say that $e$ is a negative edge of $c$ if

$$\det \binom{t(x)}{n(x)} \lt 0$$

(the cell $c$ is “to the right” as $i$ is traversed along $e$) and a positive edge if

$$\det \binom{t(x)}{n(x)} \gt 0$$

(the cell $c$ is to the left).

Power shows that under the progressivity conditions, for each $c \in C_2$ there are unique distinct vertices $u, v$ such that the negative edges of $c$ form a directed path $\alpha \in F(Q)(u, v)$ from $u$ to $v$, and the positive edges of $c$ form a directed path $\beta \in F(Q)(u, v)$. We then define $\sigma(c) = \alpha$ and $\tau(c) = \beta$.

Power’s pasting theorem may be stated in the following form:

Theorem

For every pasting scheme $(Q, i)$, the free 2-category on the 2-computad $Comp(Q, i)$ has exactly one 2-morphism $\gamma$ whose $0$-domain is the source of $Q$, whose $0$-codomain is the sink of $Q$, whose $1$-domain of $\gamma$ is the directed path consisting of positive edges of the unique unbounded component of $\mathbb{R}^2 \setminus i(R(Q))$, and whose $1$-codomain is the directed path consisting of negative edges of that component.

Related concepts

• pasting diagram

• pasting law for pullbacks/homotopy pullbacks

References

The notion of pasting in a 2-category was introduced in

• Jean Bénabou, Introduction to bicategories, in Lecture Notes in Mathematics Vol. 47, pp. l-77, Springer-Verlag, New York/Berlin, (1967)

• Michael Johnson: Pasting Diagrams in $n$-Categories with Applications to Coherence Theorems and Categories of Paths, Doctoral Thesis, University of Sydney, 1987

• Michael Johnson: The Combinatorics of $n$-Categorical Pasting, Journal of Pure and Applied Algebra 62 (1989)

• John Power: A 2-Categorical Pasting Theorem, Journal of Algebra 129 (1990)

Other notions of pasting presentations have been given by Street (parity complexes) and by Steiner,

• Ross Street, Parity complexes, Cahiers Top. Géom Diff. Catégoriques 32 (1991), 315-343. (link) Corrigenda, Cahiers Top. Géom Diff. Catégoriques 35 (1994), 359-361. (link)

• Richard Steiner, The algebra of directed complexes, Appl. Cat. Struct. 1 (1993), 247-284.